// Implementation of Dijkstra and Kruskal Algorithms
// Vertices are labled with integers starting with 0

#include <vector>
#include <list>
#include <set>
#include <limits>

#include <iostream>

using namespace std;


typedef int vertex_t;
typedef double weight_t;
const weight_t max_weight = numeric_limits<double>::infinity();
typedef int priority_t;


class Edge {
	vertex_t u;
	vertex_t v;
	weight_t w;
public:
	Edge(vertex_t v1, vertex_t v2, weight_t weight)
	{
		u = v1;
		v = v2;
		w = weight;
	}
	weight_t getWeight() { return w; }
	void setWeight(weight_t w) { this->w = w; }
	vertex_t either() { return u; }
	vertex_t other(vertex_t u)
	{
		if (this->u == u) return v;
		else if (this->v == u) return u;
		else return -1; //exit(1);
	}
	// Comparator for the edge class to apply for templation
	struct Comparator {
		// This method is useful to be injected into set template
		bool operator() (const Edge &left, const Edge &right)
		{
			vertex_t lEither = left.either();
			vertex_t lOther = left.other(lEither);
			vertex_t rEither = right.either();
			vertex_t rOther = right.other(rEither);
			if (left.w == right.w) {
				if (lEither == rEither && lOther==rOther ||
					lEither == rOther && lOther==rEither) {
					return 0;
				} else {
					return lEither < rEither || lOther < rOther;
				}
			}
			return left.w < right.w;
		}
	};
};

/*
UF class is used by Minimum Spanning Tree algorithm for intermediate operations
on the the graph components
*/ 
class UF
{
	int id[];
	short rank[];
	int count;
public:
	UF(int n)
	{
		count = n;
		//id = int[n];
		//rank = new short[n];
		for (int i = 0; i < n; i++) {
			id[i] = i;
			rank[i] = 0;
		}
	}
	
	// Return component identifier for a given node
	int find(int p)
	{
		while(p != id[p]) {
			id[p] = id[id[p]];
			p = id[p];
		}
		return p;
	}

	// Return number of components
	int getCount()
	{
		return count;
	}

	// Checks if the two nodes are connected
	bool connected(int p, int q)
	{
		return id[p] == id[q];
	}

	// Merge the components containing p and q
	void union_(int p, int q)
	{
		int i = find(p);
		int j = find(q);
		if (i == j) return;
		if      (rank[i] < rank[j]) id[i] = j;
		else if (rank[i] > rank[j]) id[j] = i;
		else {
			id[j] = i;
			rank[i]++;
		}
		count--;
	}
};

/*
Abstract Data Structure representing a graph
*/
class Graph {
	int v; // Number of vertices
	int e; // Number of edges
	vector < vector < Edge > > adjList; // The adjacency list

public:
	// Consruct a graph of with n vertices
	Graph(int n)
	{
		v = n;
		e = 0;
		adjList.resize(n);
	}

	// Returns the number of vertices in the graph
	int V()
	{
		return v;
	}

	//Returns the number of edges in the graph
	int E()
	{
		return e;
	}

	// tests whether there is an edge from node x to node y.
	bool adjacent(vertex_t x, vertex_t y)
	{
		for(vector<Edge>::iterator it = adjList[x].begin();
				it != adjList[x].end();
				it++) {

			if(it->other(x) == y) return true;
		}
		return false;
	}

	// lists all neighbors y such that there is an edge from x to y.
	vector<Edge> getNeighbors(vertex_t x)
	{
		return adjList[x];
	}

	// adds to G the edge from x to y with weight w, if it is not there.
	void addEdge(vertex_t x, vertex_t y, weight_t w)
	{
		Edge edge(x, y, w);
		adjList[x].push_back(edge);
		e++;
	}

	// removes the edge from x to y, if it is there.
	void deleteEdge(vertex_t x, vertex_t y)
	{
		for(vector<Edge>::iterator it = adjList[x].begin();
				it != adjList[x].end();
				it++) {
			if(it->other(x) == y) adjList[x].erase(it);
		}
		e--;
	}

	// returns the weight associated to the edge (x,y).
	// If there is not edge between x and y return 0
	weight_t getWeight(vertex_t x, vertex_t y)
	{
		for (vector<Edge>::iterator it = adjList[x].begin();
				it != adjList[x].end();
				it++) {
			if(it->other(x) == y) return it->getWeight();
		}
		return 0;
	}

	// sets the weight associated to the edge (x,y) to w.
	void setWeight(vertex_t x, vertex_t y, weight_t w)
	{
		for (vector<Edge>::iterator it = adjList[x].begin();
				it != adjList[x].end();
				it++) {
			if(it->other(x) == y){
				it->setWeight(w);
			}
		}
	}

	// Return a vector of edges of this graph
	vector<Edge> getEdges()
	{
		vector<Edge> edges;
		for (vector<vector<Edge> >::iterator outItr = adjList.begin();
			outItr != adjList.end();
			outItr++) {
			for (vector<Edge>::iterator inItr = outItr->begin();
				inItr != outItr->end();
				inItr++) {

				if(inItr->either() > inItr->other(inItr->either()))	
					edges.push_back(*inItr);
			}
		}

		return edges;
	}
	
};

/*
The Minimum spanning tree algorithm class.
*/
class SpanningTreeAlgo {
	set<Edge, Edge::Comparator> mst;
	weight_t weight;

public:
	// This constructure runs the algorithm
	SpanningTreeAlgo (Graph graph)
	{
		// Put all edges onto a priority queue
		set<Edge, Edge::Comparator> pq;
		for (vector<Edge>::iterator itr = graph.getEdges().begin();
				itr != graph.getEdges().end();
				itr++) {
			pq.insert(*itr);
		} // TODO implement a priority queue that combines erase/access
		UF uf(graph.V());
		while(!pq.empty() && mst.size() < graph.V()-1) {
			Edge e = *pq.begin();
			pq.erase(pq.begin());
			int v = e.either();
			int u = e.other(v);
			if(!uf.connected(v, u)) {
				uf.union_(u, v);
				mst.insert(e);
				weight += e.getWeight();
			}
				
		}
	}
	
	// Print the minimum spanning tree
	void print()
	{
		for (set<Edge, Edge::Comparator>::iterator it = mst.begin();
				it != mst.end();
				it++) {
			cout << "(" << it->either() << ", " << it->other(it->either()) 
				<< ", " << it->getWeight() << ")" << endl;
		}
	}

	
};

// Testing the  minimum spanning tree algorithm
void testSTA()
{
	Graph g(5);
	g.addEdge(0, 1, 4.0);
	g.addEdge(0, 2, 8.0);
	g.addEdge(1, 0, 10.0);
	g.addEdge(1, 2, 1.0);
	g.addEdge(1, 3, 2.0);
	SpanningTreeAlgo sta(g);
	sta.print();
}

int main(void)
{
	testSTA();

	return 0;
}
